{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Groups Getting Fresh Donuts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #memoization #array #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #记忆化搜索 #数组 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxHappyGroups"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #得到新鲜甜甜圈的最多组数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个甜甜圈商店，每批次都烤 <code>batchSize</code> 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 <strong>所有</strong> 甜甜圈都必须已经全部销售完毕。给你一个整数 <code>batchSize</code> 和一个整数数组 <code>groups</code> ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 <code>groups[i]</code> 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。</p>\n",
    "\n",
    "<p>当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。</p>\n",
    "\n",
    "<p>你可以随意安排每批顾客到来的顺序。请你返回在此前提下，<strong>最多</strong> 有多少组人会感到开心。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>batchSize = 3, groups = [1,2,3,4,5,6]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>batchSize = 4, groups = [1,3,2,5,2,2,1,6]\n",
    "<b>输出：</b>4\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= batchSize <= 9</code></li>\n",
    "\t<li><code>1 <= groups.length <= 30</code></li>\n",
    "\t<li><code>1 <= groups[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-groups-getting-fresh-donuts](https://leetcode.cn/problems/maximum-number-of-groups-getting-fresh-donuts/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-groups-getting-fresh-donuts](https://leetcode.cn/problems/maximum-number-of-groups-getting-fresh-donuts/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[1,2,3,4,5,6]', '4\\n[1,3,2,5,2,2,1,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res=0\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        # 解法：模拟退火\n",
    "        if batchSize==1: return len(groups)\n",
    "\n",
    "        newgroups=[]\n",
    "        res0=0\n",
    "        for group in groups:\n",
    "            if group % batchSize==0: res0+=1\n",
    "            else: newgroups.append(group%batchSize)\n",
    "\n",
    "        if len(newgroups)<=1:\n",
    "            return res0+len(newgroups)\n",
    "\n",
    "        def cal():\n",
    "            remain,thisres=0,0\n",
    "            for buy in newgroups:\n",
    "                if remain==0:\n",
    "                    thisres+=1\n",
    "                remain-=buy\n",
    "\n",
    "                if remain<0:\n",
    "                    remain+=batchSize\n",
    "            self.res=max(self.res,thisres)\n",
    "            return thisres\n",
    "\n",
    "        def simulate_annel():\n",
    "            random.shuffle(newgroups)\n",
    "            t=5e4\n",
    "            while t>1e-5:\n",
    "                i,j=random.randint(0,len(newgroups)-1),random.randint(0,len(newgroups)-1)\n",
    "                x=cal()\n",
    "                newgroups[i],newgroups[j]=newgroups[j],newgroups[i]# swap\n",
    "                y=cal()\n",
    "\n",
    "                delta=y-x\n",
    "                if delta<0:\n",
    "                    newgroups[i],newgroups[j]=newgroups[j],newgroups[i]# swap\n",
    "\n",
    "                t*=0.97\n",
    "\n",
    "        for i in range(27):\n",
    "            simulate_annel()\n",
    "        return res0+self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = 0\n",
    "        \n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        if batchSize == 1: return len(groups)\n",
    "\n",
    "        newgroups = []\n",
    "        res0 = 0\n",
    "\n",
    "        for group in groups:\n",
    "            if group % batchSize == 0: res0 += 1\n",
    "            else: newgroups.append(group % batchSize)\n",
    "        \n",
    "        if len(newgroups) <= 1: return res0 + len(newgroups)\n",
    "\n",
    "        def cal():\n",
    "            remain, thisres = 0, 0\n",
    "            for buy in newgroups:\n",
    "                if remain == 0:\n",
    "                    thisres += 1\n",
    "                remain -= buy\n",
    "                if remain < 0: remain += batchSize \n",
    "            self.res = max(self.res, thisres)\n",
    "            return thisres \n",
    "        \n",
    "        def simulate_annel():\n",
    "            random.shuffle(newgroups)\n",
    "            t = 5e4\n",
    "            while t > 1e-5:\n",
    "                x = cal()\n",
    "\n",
    "                i = random.randint(0, len(newgroups)-1)\n",
    "                j = random.randint(0, len(newgroups)-1)\n",
    "                newgroups[i], newgroups[j] = newgroups[j], newgroups[i]\n",
    "                y = cal()\n",
    "\n",
    "                delta = y - x \n",
    "                if delta < 0:\n",
    "                    newgroups[i], newgroups[j] = newgroups[j], newgroups[i]\n",
    "                \n",
    "                t *= 0.97\n",
    "    \n",
    "        for i in range(27):\n",
    "            simulate_annel()\n",
    "        return res0 + self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        # 首先统计能被batchsize整除的groups元素\n",
    "        cnt=[0]*batchSize\n",
    "        res=0\n",
    "        for v in groups:\n",
    "            v%=batchSize\n",
    "            if v==0:\n",
    "                res+=1\n",
    "            elif cnt[batchSize-v]:\n",
    "                cnt[batchSize-v]-=1\n",
    "                res+=1\n",
    "            else:\n",
    "                cnt[v]+=1\n",
    "        \n",
    "\n",
    "        bitmask=0\n",
    "        for i in range(1,batchSize):\n",
    "            bitmask += cnt[i]*31**i\n",
    "        \n",
    "\n",
    "        @cache\n",
    "        def dfs(left,bitmask):           \n",
    "            \n",
    "            ans=0\n",
    "            for i in range(1,batchSize):\n",
    "                if bitmask//31**(i)%31>0:\n",
    "                    ans=max(ans,(left==0)+dfs((left+batchSize-i)%batchSize,bitmask-31**i))\n",
    "                \n",
    "            return ans\n",
    "        \n",
    "        return res+dfs(0,bitmask)\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        \n",
    "        cnt = [0]*batchSize\n",
    "        for num in groups:\n",
    "            cnt[num%batchSize] += 1\n",
    "        \n",
    "        ans = cnt[0]\n",
    "        cnt[0] = 0\n",
    "        for i in range(1, batchSize):\n",
    "            j = batchSize-i\n",
    "            if i == j:\n",
    "                x = cnt[i]//2\n",
    "                ans += x\n",
    "                cnt[i] -= x*2\n",
    "            else:\n",
    "                x = cnt[i] if cnt[i] < cnt[j] else cnt[j]\n",
    "                ans += x\n",
    "                cnt[i] -= x\n",
    "                cnt[j] -= x\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(state, pre):\n",
    "            res = 0\n",
    "            lst = list(state)\n",
    "            for x in range(batchSize):\n",
    "                if lst[x]:\n",
    "                    lst[x] -= 1\n",
    "                    cur = int(pre==0) + dfs(tuple(lst), (pre+x)%batchSize)\n",
    "                    lst[x] += 1\n",
    "                    if cur > res:\n",
    "                        res = cur\n",
    "            return res\n",
    "        \n",
    "        return ans + dfs(tuple(cnt), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "\n",
    "        n = len(groups)\n",
    "        cnt = [0] * batchSize\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            tmp = groups[i] % batchSize\n",
    "            if tmp == 0:\n",
    "                ans += 1\n",
    "                continue\n",
    "            if cnt[batchSize - tmp]:\n",
    "                cnt[batchSize - tmp] -= 1\n",
    "                ans += 1\n",
    "            else:\n",
    "                cnt[tmp] += 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(left, cur):\n",
    "\n",
    "            cur = list(cur)\n",
    "            res = 0\n",
    "            for k, v in enumerate(cur):\n",
    "                if v > 0:\n",
    "                    cur[k] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + k + 1) % batchSize, tuple(cur)))\n",
    "                    cur[k] += 1\n",
    "            return res\n",
    "\n",
    "        return cnt[0] + ans + dfs(0, tuple(cnt[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, m: int, groups: List[int]) -> int:\n",
    "        # 1. 递归\n",
    "        # cnt = [0] * batchSize\n",
    "        # for x in groups:\n",
    "        #     cnt[x % batchSize] += 1\n",
    "        \n",
    "        # @cache #记忆化\n",
    "        # def dfs(left:int, cnt:Tuple[int]) -> int:\n",
    "        #     res = 0\n",
    "        #     cnt = list(cnt)\n",
    "        #     for x, c in enumerate(cnt): # 枚举顾客\n",
    "        #         if c: #cnt[x] > 0\n",
    "        #             cnt[x] -= 1\n",
    "        #             res = max(res, (left == 0) +dfs((left + x + 1) % batchSize, tuple(cnt))) # x从0开始这里要+1\n",
    "        #             cnt[x] += 1\n",
    "        #     return res\n",
    "        # return cnt[0] + dfs(0, tuple(cnt[1:])) # 转成tuple\n",
    "\n",
    "        # 2.位运算优化\n",
    "        ans = 0\n",
    "        cnt = [0] * m\n",
    "        for x in groups:\n",
    "            x %= m\n",
    "            if x == 0:\n",
    "                ans += 1 #直接排在最前面\n",
    "            elif cnt[-x]:\n",
    "                cnt[-x] -= 1 #配对\n",
    "                ans += 1\n",
    "            else:\n",
    "                cnt[x] += 1\n",
    "        @cache\n",
    "        def dfs(left:int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt): # 枚举顾客\n",
    "                if c: #cnt[x] > 0\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt))) # x从0开始，这里要+1\n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        return ans + dfs(0, tuple(cnt[1:])) #转成tuple 这样能记忆"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, m: int, groups: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = [0] * m\n",
    "        for x in groups:\n",
    "            x %= m\n",
    "            if x == 0:\n",
    "                ans += 1  # 直接排在最前面\n",
    "            elif cnt[-x]:\n",
    "                cnt[-x] -= 1  # 配对\n",
    "                ans += 1\n",
    "            else:\n",
    "                cnt[x] += 1\n",
    "\n",
    "        @cache  # 记忆化\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt):  # 枚举顾客\n",
    "                if c:  # cnt[x] > 0\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt)))  # x 从 0 开始，这里要 +1\n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        return ans + dfs(0, tuple(cnt[1:]))  # 转成 tuple 这样能记忆化\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, m: int, groups: List[int]) -> int:\n",
    "        ans = 0\n",
    "        cnt = [0] * m\n",
    "        for x in groups:\n",
    "            x %= m\n",
    "            if x == 0:\n",
    "                ans += 1  # 直接排在最前面\n",
    "            elif cnt[-x]:\n",
    "                cnt[-x] -= 1  # 配对\n",
    "                ans += 1\n",
    "            else:\n",
    "                cnt[x] += 1\n",
    "\n",
    "        @cache  # 记忆化\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt):  # 枚举顾客\n",
    "                if c:  # cnt[x] > 0\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt)))  # x 从 0 开始，这里要 +1\n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        return ans + dfs(0, tuple(cnt[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        m = batchSize\n",
    "        ans = 0\n",
    "        cnt = [0] * m\n",
    "        for x in groups:\n",
    "            x %= m\n",
    "            if x == 0:\n",
    "                ans += 1  # 直接排在最前面\n",
    "            elif cnt[-x]:\n",
    "                cnt[-x] -= 1  # 配对\n",
    "                ans += 1\n",
    "            else:\n",
    "                cnt[x] += 1\n",
    "\n",
    "        @cache  # 记忆化\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt):  # 枚举顾客\n",
    "                if c:  # cnt[x] > 0\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt)))  # x 从 0 开始，这里要 +1\n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        return ans + dfs(0, tuple(cnt[1:]))  # 转成 tuple 这样能记忆化"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        groups = [num % batchSize for num in groups]\n",
    "        cnt = [0]*batchSize\n",
    "        for num in groups:\n",
    "            cnt[num] += 1\n",
    "        ans = cnt[0]\n",
    "        for i in range(1, batchSize):\n",
    "\n",
    "            x = min(cnt[i], cnt[batchSize-i])\n",
    "            if i != batchSize - i:\n",
    "                ans += x\n",
    "                cnt[i] -= x\n",
    "                cnt[batchSize-i] -= x\n",
    "            else:\n",
    "                ans += x//2\n",
    "                cnt[i] %= 2\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(pre, tup):\n",
    "            res = 0\n",
    "            lst = list(tup)\n",
    "            for i in range(1, batchSize):\n",
    "                if lst[i]:\n",
    "                    lst[i] -= 1\n",
    "                    cur = int(pre==0) + dfs((pre+i)%batchSize, tuple(lst))\n",
    "                    lst[i] += 1\n",
    "                    if cur > res:\n",
    "                        res  = cur\n",
    "            return res\n",
    "\n",
    "        return ans + dfs(0, tuple(cnt))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        ans=0\n",
    "        #groups.sort(reverse=True)\n",
    "        n=len(groups)\n",
    "        d=[0]*batchSize\n",
    "        for x in groups:\n",
    "            if x%batchSize==0:\n",
    "                ans+=1\n",
    "            else:\n",
    "                d[x%batchSize]+=1\n",
    "\n",
    "        for m in range(1, batchSize//2+1):\n",
    "            if 2*m==batchSize:\n",
    "                ans+=d[m]//2\n",
    "                d[m]%=2\n",
    "                continue\n",
    "            cur=min(d[m],d[batchSize-m])\n",
    "            d[m]-=cur\n",
    "            d[batchSize-m]-=cur\n",
    "            ans+=cur\n",
    "        \n",
    "        hub=tuple((k,d[k]) for k in range(batchSize) if d[k]>0)\n",
    "        \n",
    "        @cache\n",
    "        def retr(prem,hub):\n",
    "            \n",
    "            dhub={k:v for k,v in list(hub) if v>0}\n",
    "            # print(hub, dhub)\n",
    "            if len(dhub)==0:\n",
    "                return 0\n",
    "            maxi=0\n",
    "            for k,v in dhub.items():\n",
    "                dhub[k]-=1\n",
    "                curhub=tuple(sorted(dhub.items()))\n",
    "                cur=retr((prem+k)%batchSize,curhub)\n",
    "                dhub[k]+=1\n",
    "                if cur>maxi:\n",
    "                    maxi=cur\n",
    "            return (prem==0)+maxi\n",
    "        \n",
    "        return ans+retr(0,hub)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        from functools import cache\n",
    "        \n",
    "        ct = Counter([(group % batchSize) for group in groups])\n",
    "\n",
    "        mask = (1<<5) - 1\n",
    "\n",
    "        state = 0\n",
    "        for i in range(batchSize-1, 0, -1):\n",
    "            state = (state << 5) | ct[i]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def search(state: int) -> int:\n",
    "            if state == 0:\n",
    "                return 0\n",
    "\n",
    "            total_r = 0\n",
    "            for i in range(1, batchSize):\n",
    "                total_r += i * ( (state>>(5*(i-1))) & mask )\n",
    "\n",
    "            best = 0\n",
    "            for j in range(1, batchSize):\n",
    "                decrease_state = (state>>(5*(j-1))) & mask\n",
    "                if decrease_state == 0:\n",
    "                    continue\n",
    "\n",
    "                new_state = state - (1 << (5*(j-1)))\n",
    "                val = search(new_state)\n",
    "\n",
    "                if (total_r-j) % batchSize == 0:\n",
    "                    val = val + 1\n",
    "\n",
    "                best = max(best, val)\n",
    "\n",
    "            return best\n",
    "\n",
    "        ret_val = search(state) + ct[0]\n",
    "        search.cache_clear()\n",
    "\n",
    "        return ret_val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        kWidth = 5\n",
    "        kWidthMask = (1 << kWidth) - 1\n",
    "\n",
    "        cnt = Counter(x % batchSize for x in groups)\n",
    "\n",
    "        start = 0\n",
    "        for i in range(batchSize - 1, 0, -1):\n",
    "            start = (start << kWidth) | cnt[i]\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask: int) -> int:\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "\n",
    "            total = 0\n",
    "            for i in range(1, batchSize):\n",
    "                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)\n",
    "                total += i * amount\n",
    "\n",
    "            best = 0\n",
    "            for i in range(1, batchSize):\n",
    "                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)\n",
    "                if amount > 0:\n",
    "                    result = dfs(mask - (1 << ((i - 1) * kWidth)))\n",
    "                    if (total - i) % batchSize == 0:\n",
    "                        result += 1\n",
    "                    best = max(best, result)\n",
    "\n",
    "            return best\n",
    "\n",
    "        ans = dfs(start) + cnt[0]\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        kWidth = 5\n",
    "        kWidthMask = (1 << kWidth) - 1\n",
    "\n",
    "        cnt = collections.Counter(x % batchSize for x in groups)\n",
    "\n",
    "        start = 0\n",
    "        for i in range(batchSize - 1, 0, -1):\n",
    "            start = (start << kWidth) | cnt[i]\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask: int) -> int:\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "\n",
    "            total = 0\n",
    "            for i in range(1, batchSize):\n",
    "                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)\n",
    "                total += i * amount\n",
    "\n",
    "            best = 0\n",
    "            for i in range(1, batchSize):\n",
    "                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)\n",
    "                if amount > 0:\n",
    "                    result = dfs(mask - (1 << ((i - 1) * kWidth)))\n",
    "                    if (total - i) % batchSize == 0:\n",
    "                        result += 1\n",
    "                    best = max(best, result)\n",
    "\n",
    "            return best\n",
    "\n",
    "        ans = dfs(start) + cnt[0]\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        kWidth = 5\n",
    "        kWidthMask = (1 << kWidth) - 1\n",
    "\n",
    "        cnt = Counter(x % batchSize for x in groups)\n",
    "\n",
    "        start = 0\n",
    "        for i in range(batchSize - 1, 0, -1):\n",
    "            start = (start << kWidth) | cnt[i]\n",
    "\n",
    "        @cache\n",
    "        def dfs(mask: int) -> int:\n",
    "            if mask == 0:\n",
    "                return 0\n",
    "\n",
    "            total = 0\n",
    "            for i in range(1, batchSize):\n",
    "                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)\n",
    "                total += i * amount\n",
    "\n",
    "            best = 0\n",
    "            for i in range(1, batchSize):\n",
    "                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)\n",
    "                if amount > 0:\n",
    "                    result = dfs(mask - (1 << ((i - 1) * kWidth)))\n",
    "                    if (total - i) % batchSize == 0:\n",
    "                        result += 1\n",
    "                    best = max(best, result)\n",
    "\n",
    "            return best\n",
    "\n",
    "        ans = dfs(start) + cnt[0]\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        from collections import Counter\n",
    "        from functools import cache\n",
    "        \n",
    "        ct = Counter([(group % batchSize) for group in groups])\n",
    "\n",
    "        mask = (1<<5) - 1\n",
    "\n",
    "        state = 0\n",
    "        for i in range(batchSize-1, 0, -1):\n",
    "            state = (state << 5) | ct[i]\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def search(state: int, r: int) -> int:\n",
    "            if state == 0:\n",
    "                return 0\n",
    "\n",
    "            best = 0\n",
    "            for j in range(1, batchSize):\n",
    "                decrease_state = (state>>(5*(j-1))) & mask\n",
    "                if decrease_state == 0:\n",
    "                    continue\n",
    "\n",
    "                new_state = state - (1 << (5*(j-1)))\n",
    "                val = search(new_state, (r + j) % batchSize)\n",
    "\n",
    "                if (r + j) % batchSize == 0:\n",
    "                    val = val + 1\n",
    "\n",
    "                best = max(best, val)\n",
    "\n",
    "            return best\n",
    "\n",
    "        ret_val = search(state, 0) + ct[0]\n",
    "        search.cache_clear()\n",
    "\n",
    "        return ret_val if sum(groups) % batchSize == 0 else ret_val + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        # 首先统计能被batchsize整除的groups元素\n",
    "        cnt=[0]*batchSize\n",
    "        for v in groups:\n",
    "            cnt[v%batchSize]+=1\n",
    "\n",
    "        @cache\n",
    "        def dfs(left,arr):            \n",
    "            arr=list(arr)\n",
    "            ans=0\n",
    "            for i in range(1,batchSize):\n",
    "                if arr[i]:\n",
    "                    arr[i]-=1\n",
    "                    ans=max(ans,(left==0)+dfs((left+batchSize-i)%batchSize,tuple(arr)))\n",
    "                    arr[i]+=1\n",
    "                \n",
    "            return ans\n",
    "        \n",
    "        return cnt[0]+dfs(0,tuple(cnt))\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchsize: int, groups: List[int]) -> int:\n",
    "\n",
    "        # groups[i]表示第i次的购买人数； batchsize表示每次烤的个数；每人只需要一个\n",
    "        # 随意安排顺序，使得买剩下的组数最少\n",
    "\n",
    "        # 如果前一批的顾客人数恰好为bitchsize的倍数，则本批顾客不会买到剩的\n",
    "        # 按照group[i] mod m 的结果分成m组，统计每组的元素个数，记录到cnt中，对于group[i] mod m = 0 的组，可以直接将这些顾客安排在最前\n",
    "        cnt = [0] * batchsize # batchsize (0, 9]\n",
    "        for x in groups:\n",
    "            cnt[x % batchsize] += 1 \n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int: # dfs(left, cnt): left表示上批顾客购买完成后没剩下\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt): # 枚举顾客\n",
    "                if c :  # cnt[x] > 0 \n",
    "                    cnt[x] -= 1 \n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % batchsize, tuple(cnt))) # x从0开始\n",
    "                    cnt[x] += 1 \n",
    "            return res \n",
    "        return cnt[0] + dfs(0, tuple(cnt[1:])) # 转成tuple\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "\n",
    "        n = len(groups)\n",
    "        cnt = [0] * batchSize\n",
    "        for i in range(n):\n",
    "            cnt[groups[i] % batchSize] += 1\n",
    "        \n",
    "        @cache\n",
    "        def dfs(left, cur):\n",
    "\n",
    "            cur = list(cur)\n",
    "            res = 0\n",
    "            for k, v in enumerate(cur):\n",
    "                if v > 0:\n",
    "                    cur[k] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + k + 1) % batchSize, tuple(cur)))\n",
    "                    cur[k] += 1\n",
    "            return res\n",
    "\n",
    "        return cnt[0] + dfs(0, tuple(cnt[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, m: int, groups: List[int]) -> int:\n",
    "        cnt = [0] * m\n",
    "\n",
    "        for x in groups:\n",
    "            cnt[x%m] += 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt):\n",
    "                if c:\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt)))\n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        \n",
    "        return cnt[0] + dfs(0, tuple(cnt[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, m: int, groups: List[int]) -> int:\n",
    "        cnt = [0] * m\n",
    "        for x in groups:\n",
    "            cnt[x % m] += 1\n",
    "\n",
    "        @cache  # 记忆化\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt):  # 枚举顾客\n",
    "                if c:  # cnt[x] > 0\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt)))  # x 从 0 开始，这里要 +1\n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        return cnt[0] + dfs(0, tuple(cnt[1:]))  # 转成 tuple 这样能记忆化\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        cnt = [0] * batchSize\n",
    "        for x in groups:\n",
    "            cnt[x % batchSize] += 1\n",
    "        \n",
    "        @cache #记忆化\n",
    "        def dfs(left:int, cnt:Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt): # 枚举顾客\n",
    "                if c: #cnt[x] > 0\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) +dfs((left + x + 1) % batchSize, tuple(cnt))) # x从0开始这里要+1\n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        return cnt[0] + dfs(0, tuple(cnt[1:])) # 转成tuple"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        g = [x % batchSize for x in groups]\n",
    "\n",
    "        cnts = Counter(g)\n",
    "        cnts_nz = tuple(cnts[i] for i in range(1, batchSize))\n",
    "\n",
    "        @cache\n",
    "        def dp(rem, cnt):\n",
    "            if rem == 0:\n",
    "                d = 1\n",
    "            else:\n",
    "                d = 0\n",
    "\n",
    "            t = 0\n",
    "            for i, c in enumerate(cnt):\n",
    "                if c > 0:\n",
    "                    nr = (rem + i + 1) % batchSize\n",
    "                    t = max(t, d + dp(nr, cnt[:i] + (c - 1,) + cnt[i + 1:]))\n",
    "            \n",
    "            return t\n",
    "\n",
    "        return dp(0, cnts_nz) + cnts[0]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nextgroup = []\n",
    "        for i in groups:\n",
    "            temp = i%batchSize\n",
    "            if temp == 0:\n",
    "                ans += 1\n",
    "            else:\n",
    "                nextgroup.append(temp)\n",
    "        cnt = [0] * batchSize\n",
    "        for x in nextgroup:\n",
    "            cnt[x] += 1\n",
    "\n",
    "        @cache  # 记忆化\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt):  # 枚举顾客\n",
    "                if c:  # cnt[x] > 0\n",
    "                    cnt[x] -= 1\n",
    "                    res = max(res, (left == 0) + dfs((left + x) % batchSize, tuple(cnt))) \n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        return ans + dfs(0, tuple(cnt))  # 转成 tuple 这样能记忆化\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        cnt = [0] * batchSize\n",
    "        for num in groups:\n",
    "            cnt[num % batchSize] += 1\n",
    "        # 记忆化搜索\n",
    "        @cache\n",
    "        def dfs(mod_num: int, cnt: Tuple[int]) -> int:\n",
    "            ans = 0\n",
    "            cnt = list(cnt)\n",
    "            for x ,c in enumerate(cnt):\n",
    "                # cnt[x] > 0\n",
    "                if c:\n",
    "                    cnt[x] -= 1\n",
    "                    ans = max(ans, (mod_num == 0) + dfs((mod_num + x + 1) % batchSize, tuple(cnt)))\n",
    "                    cnt[x] += 1\n",
    "            return ans\n",
    "        return cnt[0] + dfs(0, tuple(cnt[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List, Tuple\n",
    "from functools import cache\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, m: int, groups: List[int]) -> int:\n",
    "        # 记录模运算的结果\n",
    "        cnt = [0] * m\n",
    "        for x in groups:\n",
    "            cnt[x % m] += 1\n",
    "        \n",
    "        @cache  # 使用缓存来优化递归调用\n",
    "        def dfs(left: int, cnt: Tuple[int]) -> int:\n",
    "            res = 0\n",
    "            cnt = list(cnt)\n",
    "            for x, c in enumerate(cnt):  # 遍历顾客组\n",
    "                if c:  # 如果该组的人数大于0\n",
    "                    cnt[x] -= 1\n",
    "                    # 递归计算最多有多少组顾客会感到开心\n",
    "                    res = max(res, (left == 0) + dfs((left + x + 1) % m, tuple(cnt)))  \n",
    "                    cnt[x] += 1\n",
    "            return res\n",
    "        \n",
    "        return cnt[0] + dfs(0, tuple(cnt[1:]))  # 起始调用\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        g = [x % batchSize for x in groups]\n",
    "\n",
    "        cnts = Counter(g)\n",
    "\n",
    "        state0 = tuple(cnts[i] for i in range(batchSize))\n",
    "\n",
    "        @cache\n",
    "        def dp(rem, state):\n",
    "            if rem == 0:\n",
    "                happy = 1\n",
    "            else:\n",
    "                happy = 0\n",
    "\n",
    "            ret = 0\n",
    "            for i in range(1, batchSize):\n",
    "                c = state[i]\n",
    "\n",
    "                if c > 0:\n",
    "                    nt = state[:i] + (c - 1,) + state[i + 1:]\n",
    "\n",
    "                    ret = max(ret, happy + dp((rem + i) % batchSize, nt))\n",
    "\n",
    "            return ret\n",
    "\n",
    "        return dp(0, state0) + cnts[0]\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:\n",
    "        groups = [i % batchSize for i in groups]#取余\n",
    "        res = groups.count(0)#计数\n",
    "        groups = [i for i in groups if i != 0]#去除0\n",
    "        l = len(groups)\n",
    "        @lru_cache(None)\n",
    "        def dfs(state, p):#状态位，当前的余数\n",
    "            if state == 2 ** l - 1:#已遍历完\n",
    "                return 0\n",
    "            s = set()#集合存储已遍历数字\n",
    "            res = 0\n",
    "            for i in range(l):#遍历每一个\n",
    "                if state >> i & 1 == 0 and groups[i] not in s:#如果状态位为空且未在当前遍历\n",
    "                    s.add(groups[i])#更新集合\n",
    "                    res = max(res, dfs(state | 1 << i, (p + groups[i]) % batchSize))#更新状态位和余数继续深搜\n",
    "            return res + 1 if p == 0 else res#如果余数为0需要+1\n",
    "        return dfs(0, 0) + res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, size: int, groups: List[int]) -> int:\n",
    "        cnt = [0 for _ in range(size)]\n",
    "        for num in groups:\n",
    "            cnt[num % size] += 1\n",
    "        d = 0\n",
    "        for i in range(1, size):\n",
    "            d += 100 ** (i - 1) * cnt[i]\n",
    "    \n",
    "        @lru_cache(None)\n",
    "        def dfs(sum, digit):\n",
    "            if digit == 0:\n",
    "                return 0\n",
    "            res = 0\n",
    "            for i in range(1, size):\n",
    "                t = 100 ** (i - 1)\n",
    "                mod = (digit // t) % 100\n",
    "                if mod > 0:\n",
    "                    res = max(res, dfs(sum + i, digit - t))\n",
    "            if sum % size == 0:\n",
    "                res += 1\n",
    "            return res\n",
    "        return dfs(0, d) + cnt[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxHappyGroups(self, size: int, groups: List[int]) -> int:\n",
    "        cnt = [0 for _ in range(size)]\n",
    "        for num in groups:\n",
    "            cnt[num % size] += 1\n",
    "        d = 0\n",
    "        for i in range(1, size):\n",
    "            d += 100 ** (i - 1) * cnt[i]\n",
    "    \n",
    "        @cache\n",
    "        def dfs(sum, digit):\n",
    "            if digit == 0:\n",
    "                return 0\n",
    "            # if digit == 2 : \n",
    "            #     print(digit)\n",
    "            res = 0\n",
    "            for i in range(1, size):\n",
    "                t = 100 ** (i - 1)\n",
    "                mod = (digit // t) % 100\n",
    "                # if digit == 2 : \n",
    "                #     print(\"i \", i , \",mod \", mod)\n",
    "                if mod > 0:\n",
    "                    if digit == 2 : \n",
    "                        digit - t\n",
    "                    res = max(res, dfs(sum + i, digit - t))\n",
    "            if sum % size == 0:\n",
    "                res += 1\n",
    "            return res\n",
    "        return dfs(0, d) + cnt[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
